This invention relates to search engines, and particularly to prefix comparators that identify common subprefixes of two prefixes.
In application Ser. No. 09/679,313 we describe flexible search engine for a sorted binary search tree for perfect matching. The search tree is used for searching large databases, such as integrated circuit cell libraries. In application Ser. No. 09/679,209, we describe a prefix search tree that identifies the longest common subprefix of two prefixes. The prefix search tree is useful in a sorted binary search tree, such as that described in application Ser. No. 09/679,313 to perform search functions.
As described in application Ser. No. 09/679,209, the prefixes have values based on two rules: First, a bit string A is smaller in value than a bit string AB (AB greater than A), where bit string B contains at least one finite bit. Thus, if A is xe2x80x9c1101xe2x80x9d and B is xe2x80x9c110xe2x80x9d, AB is xe2x80x9c1101110xe2x80x9d which is greater than xe2x80x9c1101xe2x80x9d. Second, where two bit strings have the same length, a bit string A1B, comprising bit string A followed by binary xe2x80x9c1xe2x80x9d and a bit string B, is greater in value than the same bit string A followed by binary xe2x80x9c0xe2x80x9d and bit string C, regardless of the values of B and C. Thus, ALB greater than AOC. Thus if A is xe2x80x9c1101xe2x80x9d, B is xe2x80x9c000xe2x80x9d, and C is xe2x80x9c110xe2x80x9d, A1B is xe2x80x9c11011000xe2x80x9d and AOC is xe2x80x9c11010110xe2x80x9d and 11011000 greater than 11010110.
The prefix search tree of application Ser. No. 09/679,209 employs a mask that defines one or more common subprefixes between a binary search prefix and the binary prefixes in the vertices of the tree. A mask is derived for each prefix in the tree based on an ordered comparison of the prefix at the vertex and the search prefix. The masks are used for searching the prefix tree to find the prefix in the tree with longest matching subprefix to the search prefix.
Generation of the masks in application Ser. No. 09/679,209 requires considerable memory and processing allocation. The present invention is in an improved prefix comparator that significantly improves the performance of the mask generation.
In accordance with the invention, a longest common subprefix of two binary prefixes p1 and p2 is identified. The prefixes are defined as bit strings ip1 and n1, and ip2 and n2, respectively, where ip1 and ip2 are of equal length and represent the prefixes p1 and p2, and n1 and n2 represent the actual lengths of p1 and p2. Word portions ip1 and ip2 are processed to form a bit string having first bit values corresponding to the matching bits of ip1 and ip2. Word portions n1 and n2 are decoded to define the length of the shortest of the prefixes p1 and p2. The results of the processing of ip1 and ip2 and decoding of n1 and n2 derive a mask having a consecutive string of most significant bits having the first bit value identifying the matching subprefixes of ip1 and ip2.
A preferred aspect of the present invention is the provision of a circuit that performs the functions of the invention. Preferably, the circuit is implemented as a triangle semiconductor device.
Alternatively the present invention may be implemented as a computer readable program that is embedded in a computer usable medium to cause a computer to identify common subprefixes of two binary words and to carry out the processes of the invention.